package vn.edu.hcmut.cse.ai.search.uninformed;

import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.concurrent.LinkedBlockingDeque;
import vn.edu.hcmut.cse.ai.infrastructure.Action;
import vn.edu.hcmut.cse.ai.infrastructure.Node;
import vn.edu.hcmut.cse.ai.infrastructure.Problem;
import vn.edu.hcmut.cse.ai.infrastructure.Solution;
import vn.edu.hcmut.cse.ai.search.SearchAlgorithm;

public class BreadthFirstSearch implements SearchAlgorithm {

    @Override
    public List<Action> doSearching(Problem problem) {
        Node rootNode = new Node(problem.getInitialState(), null, null);    // TODO: action now is null
        if (problem.getGoalTest().isGoalState(rootNode.getState())) {
            return new Solution(rootNode).getActionList();    // Empty action list
        }

        Deque<Node> frontier = new LinkedBlockingDeque<>();
        frontier.addFirst(rootNode);
        HashSet<Object> exploredSet = new LinkedHashSet<>();

        while (true) {
            if (frontier.isEmpty()) {
                return new ArrayList<>();   // Empty list
            }

            Node node = frontier.removeLast();
            exploredSet.add(node.getState());
            for (Action action : problem.getActions().getActionList(node.getState())) {
                Node childNode = problem.getChildNode(node, action);
                if (!exploredSet.contains(childNode.getState())
                        && !frontier.contains(childNode)) {
                    if (problem.getGoalTest().isGoalState(childNode.getState())) {
                        return new Solution(childNode).getActionList();
                    }
                    frontier.addFirst(childNode);
                }
            }
        }
    }
}
